A Light-Based Device for Solving the Hamiltonian Path Problem

摘要

In this paper we suggest the use of light for performing useful computations.Namely, we propose a special device which uses light rays for solving theHamiltonian path problem on a directed graph. The device has a graph-likerepresentation and the light is traversing it following the routes given by theconnections between nodes. In each node the rays are uniquely marked so thatthey can be easily identified. At the destination node we will search only forparticular rays that have passed only once through each node. We show that theproposed device can solve small and medium instances of the problem inreasonable time.